package PersonStu.siqi;

/**
 * @Author：DijaH
 * @Date：2023/1/21 4:17 下午
 * @Version：1.0.0
 * @Description：
 * 给定一个字符串，能否从一个字符串中移除某些字符串变成回文字符串。返回有多少种移除方案，可以让这个字符串变为回文字符串。
 *
 * 解题：使用动态规划的方法，双层遍历，从左往右，从下往上
 */
public class code03_PhalindromeWays {

    public static int phalindromeWays(String s){
        //
        int N = s.length();
        char[] str = s.toCharArray();
        int [][] dp = new int[N][N];
        //左下角没有用，不考了，就不填充了,斜对角线
        for(int i = 0 ; i < N; i++){
            dp[i][i] = 1;
        }
        //斜对角线的上一行
        for(int i = 0; i < N - 1; i++){
            dp[i][i + 1] = str[i] == str[i+1] ? 3 : 2;
        }

        for(int i = N - 3; i >= 0; i--){
            for(int j = i + 2; j < N; j++){
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i + 1][j - 1];
                if(str[i] == str[j]){
                    dp[i][j] += dp[i + 1][j - 1] + 1;
                }
            }
        }
        return  dp[0][N-1];
    }

    public static void main(String[] args) {
        System.out.println(phalindromeWays("ABA"));
    }
}
